package puzzle.projecteuler.p200;

import java.math.BigInteger;


public class Problem160C {

	/**
	 * (10^12)!
	 * 每个数都可以写成2^a * 5^b * c的形式
	 * a <= 12*log(10)/log(2) = 39.8631 => a <= 39
	 * b <= 12*log(10)/log(5) = 17.1681 => b <= 17
	 * 满足条件的c可以是1 .. 10^12 / (2^a * 5^b)中任何一个与10互素的整数
	 * 也就是末尾数是1,3,7,9的数，而我们只需要保存末5位。
	 *    
	 * answer	: 16576
	 * time cost: 1984 ms
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();

		int[] pow = new int[100000];	//p[i]保存的是末5位是i的数的个数
		long m = 1000000000000L;
		
		for (int a = 0; a < 40; a ++) {
			for (int b = 0; b < 18; b ++) {
				BigInteger s = BigInteger.valueOf(2).pow(a);
				BigInteger t = BigInteger.valueOf(5).pow(b).multiply(s);
				if (BigInteger.valueOf(m).compareTo(t) >= 0) {
					long x = m/t.longValue();
					//1..x中末5位数是j的数的数目
					for (int j = 0; j < 100000; j ++) {
						if (j <= x) {
							if (j%10==1 || j%10==3 || j%10==7 || j%10==9) {
								pow[j] += (x-j)/100000+1;
							}
						}
					}
				}
			}
		}

		BigInteger n100000 = BigInteger.valueOf(100000);
		BigInteger r = BigInteger.ONE;
		for (int j = 0; j < 100000; j ++) {
			if (j%10==1 || j%10==3 || j%10==7 || j%10==9) {
				BigInteger t = BigInteger.valueOf(j).modPow(BigInteger.valueOf(pow[j]), n100000);
				r = r.multiply(t).mod(n100000);
			}
		}
		
		long pow2 = 0, pow5 = 0;
		long t = m;
		while (t > 0) pow2 += (t /= 2);
		t = m;
		while (t > 0) pow5 += (t /= 5);
		
		r = r.multiply(BigInteger.valueOf(2).modPow(BigInteger.valueOf(pow2-pow5), n100000)).mod(n100000);
		System.out.println(r);

		System.out.println((System.currentTimeMillis()-start) + " ms");
	}
	
}
